#ifndef SORTING_H
#define SORTING_H

#include <vector>
using namespace std;

template <typename Comparable>
double computeOrder(const vector<Comparable> &a)
{
    const int size = a.size();
    if (size <= 1)
        return 1;
    int N = 0;
    for (auto it1 = a.begin(); it1 < a.end() - 1; it1++)
        for (auto it2 = it1 + 1; it2 < a.end(); it2++)
            if (*it2 >= *it1)
                N++;
    return 2.0 * N / ((size - 1) * size);
}


/**
 * Standard heapsort.
 */
template <typename Comparable>
void percDown(vector<Comparable> &a, int i, int n);
inline int leftChild(int i);
template <typename Comparable>
void heapsort(vector<Comparable> &a)
{
    for (int i = a.size() / 2 - 1; i >= 0; --i) /* buildHeap */
        percDown(a, i, a.size());
    for (int j = a.size() - 1; j > 0; --j)
    {
        std::swap(a[0], a[j]); /* deleteMax */
        percDown(a, 0, j);
    }
}

template <typename Comparable>
void heapsort(vector<Comparable> &a, int left, int right)
{
    for (int i = (right - left + 1) / 2 - 1; i >= 0; --i) /* buildHeap */
        percDown(a, i, a.size());
    for (int j = right - left; j > 0; --j)
    {
        std::swap(a[0], a[j]); /* deleteMax */
        percDown(a, 0, j);
    }
}
/**
 * Internal method for heapsort.
 * i is the index of an item in the heap.
 * Returns the index of the left child.
 */
inline int leftChild(int i)
{
    return 2 * i + 1;
}

/**
 * Internal method for heapsort that is used in
 * deleteMax and buildHeap.
 * i is the position from which to percolate down.
 * n is the logical size of the binary heap.
 */
template <typename Comparable>
void percDown(vector<Comparable> &a, int i, int n)
{
    int child;
    Comparable tmp;

    for (tmp = std::move(a[i]); leftChild(i) < n; i = child)
    {
        child = leftChild(i);
        if (child != n - 1 && a[child] < a[child + 1])
            ++child;
        if (tmp < a[child])
            a[i] = std::move(a[child]);
        else
            break;
    }
    a[i] = std::move(tmp);
}

/**
 * Internal insertion sort routine for subarrays
 * that is used by quicksort.
 * a is an array of Comparable items.
 * left is the left-most index of the subarray.
 * right is the right-most index of the subarray.
 */
template <typename Comparable>
void insertionSort( vector<Comparable> & a, int left, int right )
{
    for( int p = left + 1; p <= right; ++p )
    {
        Comparable tmp = std::move( a[ p ] );
        int j;

        for( j = p; j > left && tmp < a[ j - 1 ]; --j )
            a[ j ] = std::move( a[ j - 1 ] );
        a[ j ] = std::move( tmp );
    }
}

/**
 * Return median of left, center, and right.
 * Order these and hide the pivot.
 */
template <typename Comparable>
const Comparable &median3(vector<Comparable> &a, int left, int right)
{
    int center = (left + right) / 2;

    if (a[center] < a[left])
        std::swap(a[left], a[center]);
    if (a[right] < a[left])
        std::swap(a[left], a[right]);
    if (a[right] < a[center])
        std::swap(a[center], a[right]);

    // Place pivot at position right - 1
    std::swap(a[center], a[right - 1]);
    return a[right - 1];
}

/**
 * Internal quicksort method that makes recursive calls.
 * Uses median-of-three partitioning and a cutoff of 10.
 * a is an array of Comparable items.
 * left is the left-most index of the subarray.
 * right is the right-most index of the subarray.
 */
template <typename Comparable>
void quicksort(vector<Comparable> &a, int left, int right)
{
    if (left + 10 <= right)
    {
        const Comparable &pivot = median3(a, left, right);

        // Begin partitioning
        int i = left, j = right - 1;
        for (;;)
        {
            while (a[++i] < pivot)
            {
            }
            while (pivot < a[--j])
            {
            }
            if (i < j)
                std::swap(a[i], a[j]);
            else
                break;
        }

        std::swap(a[i], a[right - 1]); // Restore pivot

        quicksort(a, left, i - 1);  // Sort small elements
        quicksort(a, i + 1, right); // Sort large elements
    }
    else // Do an insertion sort on the subarray
        insertionSort(a, left, right);
}

/**
 * Quicksort algorithm (driver).
 */
template <typename Comparable>
void quicksort(vector<Comparable> &a)
{
    quicksort(a, 0, a.size() - 1);
}

template <typename Comparable>
inline bool isOrdered(const vector<Comparable> &a, int left, int right)
{
    for(int i = left; i< right ;i++)
    {
        if(a[i]>a[i+1])
            return false;
    }
    return true;
}

/**
 * Internal quicksort method that makes recursive calls.
 * Uses median-of-three partitioning and a cutoff of 10.
 * a is an array of Comparable items.
 * left is the left-most index of the subarray.
 * right is the right-most index of the subarray.
 */
template <typename Comparable>
void AdvancedQuicksort(vector<Comparable> &a, int left, int right)
{
    if(isOrdered(a,left,right))
        return;
    if (left + 10 <= right)
    {
        const Comparable &pivot = median3(a, left, right);

        // Begin partitioning
        int i = left, j = right - 1;
        for (;;)
        {
            while (a[++i] < pivot)
            {
            }
            while (pivot < a[--j])
            {
            }
            if (i < j)
                std::swap(a[i], a[j]);
            else
                break;
        }

        std::swap(a[i], a[right - 1]); // Restore pivot

        quicksort(a, left, i - 1);  // Sort small elements
        quicksort(a, i + 1, right); // Sort large elements
    }
    else // Do an insertion sort on the subarray
        heapsort(a, left, right);    
}

/**
 * Quicksort algorithm (driver).
 */
template <typename Comparable>
void AdvancedQuicksort(vector<Comparable> &a)
{
    AdvancedQuicksort(a, 0, a.size() - 1);
}


#endif